package my.algorithms.mcorrea.graphs;

import java.util.*;

/**
 * Directed Graph
 * @author mcorrea
 */
public class Graph {

	private Map<Integer, Node> nodes;
	
	public Graph(){
		this.nodes = new HashMap<Integer,Node>();
	}
	
	public void addNode(Node n){
		this.nodes.put(n.getValue(), n);
	}
	
	public Map<Integer, Node> getNodes(){
		return nodes;
	}
	
	//version with Colors
	public void DFS(){
		//init step
		for(Integer k: nodes.keySet()){
			nodes.get(k).setColor(Node.Color.WHITE);
		}
		
		//start visiting
		for(Integer k: nodes.keySet()){
			if(nodes.get(k).getColor() == Node.Color.WHITE){
				DFSVisit(k);
			}
		}
		
	}
	
	private void DFSVisit(int u){
		nodes.get(u).setColor(Node.Color.GREY);
		for( int v:  nodes.get(u).getEdges()  ){
			if(nodes.get(v).getColor() == Node.Color.WHITE){
				DFSVisit(v);
			}
		}
		nodes.get(u).setColor(Node.Color.BLACK);
		System.out.print(u + " ");
	}
	
	
	//no colors, using temportal Array. takes extra O(|v|) space
	public void DFS2(){
		//init
		boolean[] visited = new boolean[nodes.size()+1];
		Arrays.fill(visited, false);
		
		for(Integer k: nodes.keySet()){
			if(!visited[k]){
				DFSVisit2(k, visited);
			}
		}
		
	}
	
	public void DFSVisit2(Integer v, boolean[] visited){
		visited[v] = true;
		//check edges
		for(Integer e: nodes.get(v).getEdges()){
			if(!visited[e]){
				DFSVisit2(e, visited);
			}
		}
		
	}
	
	
	//BFS - assumes the graph is connected
	public void BFS(Integer root){
		Queue<Integer> q = new PriorityQueue<Integer>();
		boolean[] marked = new boolean[nodes.size()];
		Arrays.fill(marked, false);
		q.add( root );
		marked[root] = true;
		while(!q.isEmpty()){
			Integer d = q.poll(); 
			// search codition met? not implemeneted. visit all the tree by default
			for(Integer edge: nodes.get(d).getEdges()){
				if(!marked[edge]){
					marked[edge] = true;
					q.add(edge);
				}
			}
		}
		System.out.println();
	}
	
	
	public static void main(String args[]){
		Graph g = new Graph();
		Node n1 = new Node(1);
		n1.addEdges( 2, 3);
		Node n2 = new Node(2);
		n2.addEdges(3);
		Node n3 = new Node(3);		
		g.addNode(n1);
		g.addNode(n2);
		g.addNode(n3);
		
		g.addNode(new Node(4));
		
		for(Integer k: g.getNodes().keySet()){
			System.out.println(g.getNodes().get(k));
		}
		
		g.DFS();
		System.out.println();
		
		for(Integer k: g.getNodes().keySet()){
			System.out.println(g.getNodes().get(k).getColor());
		}
		
		
		g.DFS2();
		
		g.BFS(1);
		
	}
	
}
